1. Field of the Invention
The present invention is directed generally to data packet networks. In particular, the present invention is directed to methods for generating routing information.
2. Description of the Related Art
In a packet switched network, routing protocols determine the path that packets traverse through the network. These routing protocols react to changes in the network (e.g., links going up and down, or link costs changing) and adjust the routes taken by packets through the network. The routing protocols are often distributed, in that they are implemented in a coordinated fashion by many routers in the network. The routing protocols are also dynamic, in that they react to changes in the network. As such, the routes taken by packets will change over time, often in unanticipated ways. In such a network, it is important to understand the nature of routing changes, as these changes impact the stability of the network and the level of service (i.e., loss and delay) experienced by packets. Network operators and service providers have invested a great deal in understanding the dynamics and stability of routing within their networks.
Previous approaches to monitoring the state of routing in the network include: 1. Monitoring of routing protocol message exchanges by specialized route monitors, then inferring the state of routing in the network based on the protocol messages; 2. Monitoring of router log messages that identify when events (e.g., link failures) have occurred; and 3. Active end-to-end measurement of the data plane to infer the stability and performance of the network. The approaches 1 and 2 measure the control plane directly but are unable to give precise information about the data plane on short time scales. That is, they can identify that changes have occurred, but they can neither precisely assess the impact of those changes nor can they necessarily determine when the impact was experienced at each individual router. The third approach measures the impact of routing changes on the data plane, but only in a coarse and imprecise manner.